#include <iostream>

using namespace std;

void myPrint(int arr[])
{
    for (int i = 0; arr[i] != '\0'; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void mySwap(int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//选择排序
/*
0~Size-1;
1~Size-1;
2~Size-1;
*/
void selectSort(int arr[], int Size)
{
    if (arr == nullptr || Size < 2)
    {
        return;
    }
    for (int i = 0; i < Size; i++)
    {
        int minValueIndex = i;
        for (int j = i + 1; j < Size; j++)
        {
            minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
        }
        mySwap(arr, i, minValueIndex);
    }
}

//冒泡排序
/*
0~Size-1;
0~Size-2;
0~Size-3;
*/
void bubbleSort(int arr[], int Size)
{
    if (arr == nullptr || Size < 2)
    {
        return;
    }
    for (int i = Size - 1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                mySwap(arr, j, j + 1);
            }
        }
    }
}

//插入排序
/*
0~1 2
0~2 3
0~3 4
*/
void insertSort1(int arr[], int Size)
{
    if (arr == nullptr || Size < 2)
    {
        return;
    }
    for (int i = 1; i < Size; i++)
    {
        int newNum = i;
        while (i - 1 >= 0 && arr[newNum] < arr[newNum - 1])
        {
            mySwap(arr, newNum, newNum - 1);
            newNum--;
        }
    }
}

void insertSort2(int arr[], int Size)
{
    for (int i = 1; i < Size; i++)
    {
        for (int pre = i - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--)
        {
            mySwap(arr, pre, pre + 1);
        }
    }
}

int main()
{
    int arr[] = {48, 38, 65, 97, 76, 13, 27, 49, 55, 04};
    // selectSort(arr, 11);
    // bubbleSort(arr, 11);
    // insertSort1(arr, 11);
    insertSort2(arr, 11);
    myPrint(arr);
    system("pause");
    return 0;
}